2169-得到 0 的操作数

给你两个 非负 整数 num1 和 num2 。

每一步 操作 中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1
。

• 例如，num1 = 5 且 num2 = 4 ，应该用 num1 减 num2 ，因此，得到 num1 = 1 和 num2 = 4 。然而，如果 num1 = 4且 num2 = 5 ，一步操作后，得到 num1 = 4 和 num2 = 1 。

返回使 num1 = 0 或 num2 = 0 的 操作数 。

示例 1：

**输入：** num1 = 2, num2 = 3
**输出：** 3
**解释：**
- 操作 1 ：num1 = 2 ，num2 = 3 。由于 num1 < num2 ，num2 减 num1 得到 num1 = 2 ，num2 = 3 - 2 = 1 。
- 操作 2 ：num1 = 2 ，num2 = 1 。由于 num1 > num2 ，num1 减 num2 。
- 操作 3 ：num1 = 1 ，num2 = 1 。由于 num1 == num2 ，num1 减 num2 。
此时 num1 = 0 ，num2 = 1 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 3 。

示例 2：

**输入：** num1 = 10, num2 = 10
**输出：** 1
**解释：**
- 操作 1 ：num1 = 10 ，num2 = 10 。由于 num1 == num2 ，num1 减 num2 得到 num1 = 10 - 10 = 0 。
此时 num1 = 0 ，num2 = 10 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 1 。

提示：

• 0 <= num1, num2 <= 105

方法一：辗转相除

思路与算法

我们可以按要求模拟两数比较后相减的操作，但在两数差距十分悬殊时，会有大量连续且相同的相减操作，因此我们可以对模拟的过程进行优化。

不妨假设 num}_1 \ge \textit{num}_2，则我们需要用 num}_1 减 num}_2，直到 num}_1 < \textit{num}_2 为止。当上述一系列操作结束之后，num}_1 的新数值即为 num}_1 \bmod \textit{num}_2，在这期间进行了 \lfloor \textit{num}_1 / \textit{num}_2 \rfloor 次相减操作，其中 \lfloor\dots\rfloor 代表向下取整。

容易发现，题目中的过程即为求两个数最大公约数的「辗转相减」方法，而我们需要将它优化为时间复杂度更低的「辗转相除」法，同时利用前文的方法统计对应相减操作的次数。

具体而言，在模拟的过程中，我们用 res 来统计相减操作的次数。在每一步模拟开始前，我们需要保证 num}_1 \ge \textit{num}_2；在每一步中，两个数 (\textit{num}_1, \textit{num}_2) 变为 (\textit{num}_1 \bmod \textit{num}_2, \textit{num}_2)，同时我们将 res 加上该步中相减操作的次数 \lfloor \textit{num}_1 / \textit{num}_2 \rfloor；最后，我们还需要交换 num}_1 与 num}_2 的数值，以保证下一步模拟的初始条件。当 num}_1 或 num}_2 中至少有一个数字为零时，循环结束，我们返回 res 作为答案。

细节

在第一步模拟（进入循环）之前，我们事实上不需要保证 num}_1 \ge \textit{num}_2，因为我们可以通过额外的一步模拟将 (\textit{num}_1, \textit{num}_2) 变为 (\textit{num}_2, \textit{num}_1)，而这一步贡献的相减次数为 0。

代码

[sol1-C++]

class Solution {
public:
    int countOperations(int num1, int num2) {
        int res = 0;   // 相减操作的总次数
        while (num1 && num2) {
            // 每一步辗转相除操作
            res += num1 / num2;
            num1 %= num2;
            swap(num1, num2);
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        res = 0   # 相减操作的总次数
        while num1 and num2:
            # 每一步辗转相除操作
            res += num1 // num2
            num1 %= num2
            num1, num2 = num2, num1
        return res

复杂度分析

• 时间复杂度：O(\log \max(\textit{num}_1, \textit{num}_2))。即为模拟辗转相除并统计操作次数的时间复杂度。

• 空间复杂度：O(1)。